Distributed digital computers and microprocessors have been used for embedded real time applications such as space vehicle systems, image processing and transmission, and integration of expert systems into avionics and industrial process control. Such distributed systems have stringent timing requirements because they often operate in real time. Timing failures in these systems are impermissible since such failures may produce catastrophic results.
The key to success in using a distributed system for these applications is the timely execution of computation tasking more than one microprocessor node as well as the communication of computed results and information among the nodes. End-to-end deadline guarantees are not possible without a communication network that supports the timely delivery of inter-task messages. Therefore, it is important that messages can be guaranteed to be transmitted to their destinations before their deadlines.
A particular protocol for real time communication between distributed nodes have recently received recognition as the ANSI standard for such systems. The protocol is the FDDI (Fiber Distributed Data Interface) token ring media access control, the details of which are available by consulting FDDI Token Ring Media Access Control (MAC). ANSI Standard X3.139, 1987. This protocol is suitable for real time applications not only because of its use in high capacity networks, but also due to the fact that it has the important property of bounded access time. Bounded access time is necessary for real time communications. The timed token protocol has been incorporated into many network standards, including the Fiber Distributed Data Interface (FDDI), IEEE 802.4, the High-Speed Data Bus and the High-Speed Ring Bus (HSDB/HSRB), and the Survivable Adaptable Fiber Optic Embedded Network (SAFENET). Many embedded real time applications use them as backbone networks. For example, the FDDI has been selected as a backbone network for NASA's Space Station Freedom.
With the timed token protocol, messages are grouped into two separate classes: synchronous and asynchronous. Synchronous messages arrive in the system at regular intervals and may be associated with deadline constraints. Timed token protocol is primarily concerned with the control of the token rotation time, which is defined as the time between two consecutive visits of the token to a particular node. At network initialization time, a protocol parameter called Target Token Rotation Time (TTRT) is determined which indicates the expected token rotation time. Each station is assigned a fraction of the TTRT, known as synchronous bandwidth, which is the maximum time for which a node is permitted to transmit its synchronous messages every time it receives the token. Once a node receives the token, it transmits its synchronous message, if any, for a time no more than its allocated synchronous bandwidth. It can then transmit its asynchronous messages only if the time elapsed since the previous token departure from the same node is less than the value of TTRT, i.e., only if the token arrived earlier than expected.
Guaranteeing a message deadline implies transmitting the message before its deadline. With a token passing protocol, a node can transmit its messages only when it captures the token. This implies that if a message deadline is to be guaranteed, the token should visit the node where the message is waiting before the expiration of the message's deadline. That is, in order to guarantee message deadlines in a token ring network, it is necessary to bound the time between two consecutive visits of the token to a node or the token rotation time. However, merely setting a limit for the token rotation time does not guarantee meeting message deadlines. A node with inadequate synchronous bandwidth may be unable to complete the transmission of a synchronous message before its deadline. On the other hand, allocating excess amounts of synchronous bandwidth to the nodes could increase the token rotation time, which may also cause message deadlines to be missed. Thus, guaranteeing message deadlines is also dependent on the appropriate allocation of synchronous bandwidth to the nodes in the distributed system.
It is widely recognized in the art of real time distributed systems that the allocation of synchronous bandwidth is an open problem with no known solution. Accordingly, it is desirable to provide a method for synchronous bandwidth allocation in a real time distributed system which guarantees message deadlines are met. Such a bandwidth allocation method should be especially compatible with the timed token protocol in order to adhere to industry standard requirements.